#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:

    // 446. 等差数列划分 II - 子序列
    // https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        unordered_map<long, vector<int>> hash; // <元素, 下标>
        for (int i = 0; i<n; ++i)
        {
            hash[nums[i]].push_back(i);
        }

        vector<vector<int>> dp(n, vector<int>(n));
        int ans = 0;

        for (int j = 2; j<n; ++j)
        {
            for (int i = 1; i<j; ++i)
            {
                long a = (long)2*nums[i] - nums[j];
                if (hash.count(a))
                {
                    for (auto k : hash[a])
                    {
                        if (k < i)
                            dp[i][j] += dp[k][i] + 1;
                    }
                }
                ans += dp[i][j];
            }
        }

        return ans;
    }
};